package week02

// 74. 搜索二维矩阵
// https://leetcode-cn.com/problems/search-a-2d-matrix/

func searchMatrix(matrix [][]int, target int) bool {
	// 行二分：确定在哪一行
	// 列二分：确定数是否存在
	var x = -1
	var left, right = 0, len(matrix)
	for left < right {
		var mid = (right - left) >> 1 + left
		if matrix[mid][0] == target || matrix[mid][len(matrix[mid])-1] == target {
			return true
		}
		if matrix[mid][0] < target && matrix[mid][len(matrix[mid])-1] > target {
			x = mid
			break
		}
		if matrix[mid][0] > target {
			right = mid
		} else {
			left = mid + 1
		}
	}
	if x == -1 {
		return false
	}

	left, right = 0, len(matrix[x])
	for left < right {
		var mid = (right - left) >> 1 + left
		if matrix[x][mid] == target {
			return true
		}
		if matrix[x][mid] > target {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return false
}